Forward error correction (FEC) is a system of error control for data transmission often used in telecommunications applications. Convolutional coding is a type of FEC code in which each m-bit information symbol to be encoded is transformed into an n-bit symbol, where “n” is greater than or equal to “m” and “m/n” is referred to as the code rate. Data encoded using convolutional encoding is generally decoded with a trellis decoder, such as a Viterbi decoder or a Turbo decoder. A trellis decoder operates by constructing a trellis of state probabilities and branch metrics. After a computational latency, the results generated by the trellis decoder in a forward direction are read in a reverse order to find the maximal likelihood path through the trellis.
A Viterbi decoder, for example, typically includes a branch metric block, or circuit, a path metric block, and a traceback block. The branch metric block provides cost information for the data coming into the decoder. The path metric block can be implemented as an add-compare-select (ACS) block that compares the costs of the branches of the trellis. The traceback block traces back through the branches of the trellis according to ACS block comparisons to find the optimum path through the trellis to enable decoding of the data.
Turbo decoders also utilize ACS blocks to compare the costs through the trellis. A Turbo decoder will generally process the trellis in a forward and reverse direction in order to optimize the path through the trellis. In some variations of a Turbo decoder, the ACS block will be modified to incorporate an offset unit that can help to increase the performance of the algorithm. In such cases, the ACS block is referred to as an add-compare-select-offset (ACSO) block. A Turbo decoder can also utilize the output of one ACS block as the input to another. A typical difference between a Viterbi decoder ACS block and a Turbo decoder ACS block is that a Viterbi decoder ACS block will select a minimum cost, while the Turbo decoder ACS block will select a maximum cost.
Accordingly, ACS blocks can compare costs of various paths of the trellis to aid in selecting one path over another. FIG. 1 is a block diagram illustrating a simplified trellis 100. Each state probability, or “state”, of the trellis 100 is shown as a circular node and is associated with a cost. For example, state 105 is associated with “Previous Cost 1” and state 110 is associated with “Previous Cost 2”. The state 115 will be associated with the “New Cost” when computed and/or selected. The cost of a given state can be calculated from the cost of previous states which are added to the cost of the branches, called branch metrics, from the previous state to the current state.
With reference to FIG. 1, the “New Cost” of state 115 can be determined as the optimal path from either state 105 or state 110. The cost of moving from state 105 to state 115 can be calculated as the sum of the “Previous Cost 1” and the “Branch Metric 1”. The cost of moving from state 110 to state 115 can be calculated as the sum of the “Previous Cost 2” and the “Branch Metric 2”. The “optimal path” can be one that is, for example, the minimal cost path or the maximum cost path. The “New Cost” result from the trellis 100 can be selected as the current cost and can be provided or used in further cost calculations.
FIG. 2 is a block diagram illustrating a conventional ACS block 200 which can be incorporated into a trellis decoder. As shown, the ACS block 200 can include two adders 205 and 210, a comparator 215, and a multiplexer 220. A register 225 also can be placed at the output of the multiplexer 220. For illustration and ease of reference, the various inputs to, and output from, the ACS block 200 are labeled in a manner that corresponds to the trellis illustrated in FIG. 1. As noted, the result “New Cost” can be provided to further ACS blocks of the trellis decoder for use in decoding received data.
The adder 205 provides an output which is the sum of the “Previous Cost 2” and the “Branch Metric 2”. The adder 210 provides an output which is the sum of the “Previous Cost 1” and the “Branch Metric 1”. The comparator 215 generates the select signal as output which is provided to the multiplexer 220. The select signal is determined according to the expression “Select Signal=(Previous Cost 2+Branch Metric 2)−(Previous Cost 1+Branch Metric 1)”. Typically, the select signal is the most significant bit (MSB) of the subtraction. The ACS further provides an output indicating the selected path. This output, however, may not be used in every case, for example, in the case of typical Turbo decoding.
When implementing ACS block 200 in hardware, one consideration is the size of the ACS block. For example, within a circuit designed for performing Viterbi error correction with a standard constraint length of 7, a Viterbi decoder would require 64 ACS blocks. As another example, a Viterbi decoder with a constraint length of 9, as is commonly used in the 3rd Generation Mobile System Standards promulgated by the 3rd Generation Partnership Project (3GPP), would require 256 ACS blocks. In view of the number of ACS blocks needed to implement decoder circuits, it can be seen that the size of the ACS block can significantly influence the size of the decoder.
Another consideration is the speed of the ACS block. The critical paths of circuits within the decoder typically are located in the feedback loop between ACS blocks. For example, with reference to FIG. 2, the critical path would begin at the output from the register 225 of ACS block 200 and continue through a subsequent ACS block. That is, the critical path typically starts at register 225 and continues through another adder, another comparator, and another multiplexer corresponding to the next ACS block in the decoder. Decreasing critical path lengths within the ACS block can contribute to faster decoders.